package com.example.demo.leetcode.codetop.bytedance;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/21 14:57
 */
public class 括号生成 {


    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        process(0,n,list,"");
        return list;
    }

    public static void process(int leftnum, int n, List<String> list,String str){

        if(leftnum ==0 && str.length() == n*2){
            list.add(str);
            return;
        }
        if(str.length() >n * 2){
            return;
        }

        if(leftnum > n){
            return;
        }

        if(leftnum > 0){
            //可以加 左括号 也可以加右括号
            process(leftnum+1,n,list,str+"(");
            process(leftnum-1,n,list,str+")");
        }else{
            //只能加左括号
            process(leftnum+1,n,list,str+"(");
        }
    }





    public static void main(String[] args) {

        List<String> strings = generateParenthesis(4);
        for(String str:strings){
            System.out.println(str);
        }
    }



}
